In the electronics industry, multi-processing systems have been developed to enable a user of a system to manipulate and process information more quickly and efficiently. A multi-processing system generally includes two or more data processors which are interconnected with a system interface bus to a shared memory array. Each of the data processors may contain a data cache to reduce the amount of data transferred between each component of the multi-processing system and to improve access times from the data processors to the memory array. Generally, the data cache includes a cache controller, a data tag cache, and a snoop tag cache. The data tag cache unit services internal memory requests from execution units in the data processor to determine whether an information value is currently being stored in the data cache. The data tag cache may also indicate if an information value stored in the data cache is valid. The snoop tag cache unit monitors, or "snoops," transactions on the system interface bus to maintain data coherency between each element of the multi-processing system. Each information value modified by an external processor must be snooped in order to maintain data coherency throughout the entire multi-processing system. Additionally, the cache controller controls operation of the data cache.
In multi-processing systems, conflicts may occur during reading and writing operations which use the data tag cache and the snoop tag cache. In a first example, assume a first data processor attempts to read data currently resident in the data cache and a second data processor attempts to simultaneously change that data. When the first data processor reads the data, a predetermined address in the data cache tag is accessed to indicate, or "point to" an address location of the data in the data cache. Similarly, when the second data processor attempts to change that data, the snoop tag cache also points to the address location in the data cache. When the same address location is accessed by the data tag cache and the snoop tag cache simultaneously, a potential for an error, or "collision" occurs. In this case, when the first data processor attempts to read the cached data at a predetermined address in the data cache tag while the second data processor attempts to write to the address, a "read/write" collision occurs.
A second example of a conflict, referred to as a "dual write collision," occurs when both data processors attempt to modify the same data simultaneously. A "dual read collision" in which both data processors attempt to read the same data may also occur. However, because a read operation generally does not modify the contents of the data cache, no error occurs. In some situations, a read operation may modify state information corresponding to the data.
Read/write and dual write collisions adversely affect the operation and performance of a multi-processing system. When a collision occurs, the cache controller typically processes the collision as an error. Therefore, rather than performing a function specified by a user of the multi-processing system, the cache controller must enable the data processor to respond to the error and subsequently provide an indeterminate response to the user. Additionally, read/write and dual write collisions are difficult to predict in a multi-processing system and, therefore, may not be easily anticipated or corrected. For more information relating to techniques used to control collisions in a multi-processing system, refer to an article entitled "Multiprocessor Cache Synchronization-Issues, Innovations, Evolution" and published on pages 424 through 433 of the IEEE Transactions on Computers in 1986. The article was written by Philip Bitar and Alvin M. Despain. Additionally, refer to a technical paper entitled "Efficient Synchronization Primitives for Large-Scale Cache-Coherent Multiprocessors" and published in the proceedings of the Third International Conference on Architectural Support for Programming Languages and Operating System on pages 64 through 75. The paper was written by James R. Goodman, Mary K. Vernon, and Philip J. Woest.
Therefore, a need exists for a cache controller which is able to resolve read/write and dual write collisions quickly and efficiently. The cache controller should also be able to fully execute each type of operation specified during a collision. For example, in a read/write collision, both the read and the write operations should be executed to provide a correct result.